Codeforces Round 263(Div. 2)

Diposting di | Edited on

传送门

A - Appleman and Easy Task （签到）

题意

判断棋盘中是否每个点四周都有偶数个‘x’

思路

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e6+50;
const ll inf=1e17;
typedef unsigned long long ull;

char s[150][150];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i]+1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int cnt=0;
            for(int k=0;k<4;k++){
                int xx=i+dx[k];
                int yy=j+dy[k];
                cnt+=s[xx][yy]=='o';
            }
            if(cnt&1)puts("NO"),exit(0);
        }
    }
    puts("YES");
    return 0;
}

B - Appleman and Card Game (贪心)

题意

可以选K个字母，价值是这个字母的数量的平方，求最大的价值

思路

平方函数斜率得知 x越大价值越大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e6+50;
const ll inf=1e17;
typedef unsigned long long ull;

char s[maxn];
int num[maxn];
int main()
{
    int n,k;
    cin>>n>>k;
    cin>>s;
    int len=strlen(s);
    ll ans=0;
    for(int i=0;i<len;i++)num[s[i]-'A']++;
    sort(num,num+26,greater<int>());
    for(int i=0;i<26;i++){
        if(num[i]){
            if(k>=num[i])k-=num[i],ans+=1LL*num[i]*num[i];
            else{
                ans+=1LL*k*k;k=0;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

C - Appleman and Toastman (贪心)

题意

AB做一个游戏，A给B一个数组，B把数组切一刀 然后再给A，如果B收到一个单独的数字就把这个数字扔掉，如果A收到一组数价值就加这组数字和

思路

贪心得每次让B把数组的最小的切掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e6+50;
const ll inf=1e17;
typedef unsigned long long ull;

ll a[maxn];

int main()
{
    int n,k;
    cin>>n;
    ll sum=0;
    priority_queue<ll,vector<ll>,greater<int> >Q;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i],Q.push(a[i]);
    sort(a+1,a+1+n);
    ll ans=0;
    while(!Q.empty()){
        ans+=sum;
        if(Q.size()>1)
            ans+=Q.top();
        sum-=Q.top();
        Q.pop();
    }
    cout<<ans<<endl;
    return 0;
}

D - Appleman and Tree (树形DP)

题意

给出一棵以0为根的树,每个节点都有可能是黑色或者白色，让你分成K部分，使得每部分都恰好有一个黑点 求方案数

思路

考虑只有两个相邻结点，A，B

如果A所在部分想要是黑色，那么他就要么自己是黑色，那就需要把B是黑色的切掉

如果A所在部分想要是黑色，那么他就要么自己是黑色，那就需要把B是白色的连接

如果A所在部分想要是黑色，那么他就要么自己是白色，那就需要把B是黑色的连接

如果A所在部分想要是白色，他们他自己只能是白色，那就需要把B是黑色的切掉

如果A所在部分想要是白色，他们他自己只能是白色，那就需要把B是白色的相连

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

vector<int>G[maxn];
int val[maxn];
ll dp[maxn][2];

void dfs(int u){
    if(val[u])dp[u][1]=1,dp[u][0]=0;
    else dp[u][0]=1,dp[u][1]=0;
    for(int i=0;i<G[u].size();i++){
        int now=G[u][i];
        dfs(now);
        ll yes=dp[u][1];
        ll no=dp[u][0];
        dp[u][1]=1LL*yes*dp[now][1]%mod;
        dp[u][1]+=1LL*yes*dp[now][0]%mod;
        dp[u][1]+=1LL*no*dp[now][1]%mod;
        dp[u][0]=1LL*no*dp[now][1]%mod;
        dp[u][0]+=1LL*no*dp[now][0]%mod;
        dp[u][1]%=mod;
        dp[u][0]%=mod;
        /*cout<<"dp[now][1]="<<dp[now][1]<<" dp[now][0]="<<dp[now][0]<<endl;
        cout<<"dp[u][1]="<<dp[u][1]<<" dp[u][0]="<<dp[u][0]<<endl;
        cout<<"yes="<<yes<<" no="<<no<<endl;*/
    }
}

int main()
{
    int n;
    cin>>n;

    for(int i=1;i<n;i++){
        int x;
        cin>>x;
        G[x].push_back(i);
    }
    for(int i=0;i<n;i++){
        cin>>val[i];
    }
    dfs(0);
    cout<<dp[0][1]<<endl;

    return 0;
}

E - Appleman and a Sheet of Paper（树状数组大模拟）

题意

给你一张纸 参考1*n的数组

然后两种操作，给你一个K，让你把左边K个数组折到右边

第二个操作 询问区间范围内的纸张厚度和

思路

因为每个操作1都会让至少一个格子变少，所以直接暴力即可

然后区间求和就可以用数据结构维护

发现操作1可能K比后面的长度还大，这时候就可以倒过来，相当于让后面N-K个折到左边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e5+50;
const int inf=1e8;

typedef unsigned long long ull;
int n,q;
int a[maxn];
bool pre;
void update(int x,int y){
    while(x<=n)a[x]+=y,x+=x&-x;
}
int sum(int x){
    int ans=0;
    while(x){
        ans+=a[x];x-=x&-x;
    }
    return ans;
}
int get(int l,int r){
    if(l>r)swap(l,r);
    return sum(r)-sum(l);
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)update(i,1);
    int cl=1,cr=n;
    while(q--){
        int t,l,r;
        cin>>t;
        if(t==1){
            int sz=cr-cl+1;
            cin>>l;
            if(l>sz/2){
                pre=!pre;
                l=sz-l;
            }
            if(pre){
                for(int j=0;j<l;j++)
                    update(cr-l-j,get(cr-l+j,cr-l+j+1));
                cr-=l;
            }
            else{
                for(int j=0;j<l;j++)
                    update(cl+l+j,get(cl+l-j-1,cl+l-j-2));
                cl+=l;
            }
        }
        else{
            cin>>l>>r;
            l++;
            if(pre)cout<<get(cr-r,cr-l+1)<<endl;
            else cout<<get(cl+l-2,cl+r-1)<<endl;
        }
    }
    return 0;
}